package hot;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author lakersUp
 * @Classname       课程表
 * @Description     拓扑排序, 依次消除入度为零的节点
 * @Date 2022/3/18 9:46
 * @Version 1.0
 */
public class Hot207canFinish {
    public boolean canFinish(int numCourses, int[][] prerequisites){
        int[] input = new int[numCourses];
//      统计入度
        for (int[] pre : prerequisites) {
            input[pre[0]]++;
        }
        //记录入度为零的节点
        Deque<Integer> queue = new LinkedList<>();
        for(int i=0;i<numCourses;i++){
            if(input[i]==0){
                queue.addLast(i);
            }
        }
//      一次消除入度为零的节点
        int count=0;
        while (!queue.isEmpty()){
            int node=queue.removeFirst();
            count++;
            for (int[] prerequisite : prerequisites) {
                if(prerequisite[1]==node){
                    input[prerequisite[0]]--;
                    if(input[prerequisite[0]]==0){
                        queue.addLast(prerequisite[0]);
                    }
                }
            }
        }

        return numCourses==count;
    }
}
